﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace sf_study
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
        }
    }


    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

    //求 二叉树的深度
    public class Solution
    {
        //递归题解

        // public int MaxDepth(TreeNode root)
        // {
        //     if (root == null)
        //     {
        //         return 0;
        //     }
        //     return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
        // }

        //层序遍历 用以前的队列存储的方法
        public int MaxDepth(TreeNode root)
        {
            List<TreeNode> que_Node = new List<TreeNode>();
            List<TreeNode> list = new List<TreeNode>();
            if (root == null)
            {
                return 0;
            }
            int deep = 1;
            que_Node.Add(root);

            while (que_Node.Count > 0)
            {
                for (int i = 0; i < que_Node.Count; i++)
                {
                    if (que_Node[i].left != null)
                    {
                        que_Node.Add(que_Node[i].left);
                    }
                    if (que_Node[i].right != null)
                    {
                        que_Node.Add(que_Node[i].right);
                    }
                }
                que_Node=list;
                deep++;
            }
            return deep;
        }
    }


}
